/*
题目: 最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

    例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

https://leetcode.cn/problems/minimum-genetic-mutation
 */
public class MinMutation {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> store = new HashSet<> ();// 仓库
        for (String x : bank)
            store.add(x);
        // 处理特殊情况
        if (!store.contains(end))   return -1;

        // 防止多次询问
        Set<String> visited = new HashSet<> ();
        // 用于更换某个字母, 需要尝试所有的可能
        char[] letters = new char[] {'A', 'C', 'G', 'T'};
        // 广度优先遍历
        Queue<String> queue = new LinkedList<> ();
        queue.offer(start);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- > 0) { // 一次修改
                StringBuilder cur = turn(queue.poll());
                // 修改每一个字母
                for (int i = 0; i < cur.length(); i++) {
                    char temp = cur.charAt(i);
                    // 尝试一个字母的所有可能
                    for (int j = 0; j < letters.length; j++) {
                        char ch = letters[j];
                        if (ch == temp) continue ;
                        cur.setCharAt(i, ch);
                        String str = cur.toString();
                        if (visited.contains(str))  continue ;
                        if (str.equals(end))    return step;

                        if (store.contains(str)) {
                            queue.offer(str);
                            visited.add(str);
                        }
                    }
                    cur.setCharAt(i, temp);
                }
            }
            step ++;
        }

        return -1;
    }

    private StringBuilder turn(String s) {
        StringBuilder ret = new StringBuilder();
        ret.append(s);
        return ret;
    }
}
